Ejercicio 1

a) Dé dos ejemplos en los cuales las técnicas de Aprendizaje Automático sean útiles y dos en los cuales no lo sean. Dé una breve justificación en cada caso.

Útiles:

IA de ajedrez: espacio de posibilidades muy amplio como para programar cada regla o procesar cada escenario.
Clasificación de spam: base de datos inicial enorme y para los programadores es imposible estar al día con las "modas" de spam.

No útiles:

Computaciones críticas y exactas con nula tolerancia a errores, ejemplo: hasheo
Problemas ya resueltos con algoritmos eficientes.

b) Elija una aplicación que considere interesante. Descríbala informalmente, y luego especifique lo más precisamente posible la tarea, la medida de performance, y la descripción de la función objetivo.

Detección de emails o mensajes de estafa.

Tarea formal: dada una cadena de caracteres S, determinar si tiene intenciones malignas con respecto a robo, estafa y engaños varios.
Medida de performance: cantidad de aciertos / intentos totales
Función objetivo: f: String -> Bool

Ejercicio 2

Se desea aprender bajo qué condiciones a Pedro le gusta ir a jugar al fútbol a la playa:

Pasted image 20230814164923.png

Con los siguientes posibles valores para cada atributo:

Cielo: Soleado, Lluvioso, Nublado
Temperatura: Templado, Frío
Humedad: Normal, Alta
Viento: Fuerte, Suave
Tmp. Agua: Templada, Fría
Tiempo: Sin cambios, Cambiante.

i. Con la forma de las hipótesis vista en el teórico: ¿cuál es el tamaño del espacio H?
ii. Calcule el espacio de versiones
iii. ¿Qué respuesta daría a las siguientes instancias?

Pasted image 20230814165907.png

i.
Cada "slot" tiene los valores del atributo + + ?.

ii. Uso Candidate-Elimination

E_0 = <Sol, Temp, Nor, Fue, Temp, Sin Camb> JUEGA=SI
S_0 = {<Sol, Temp, Nor, Fue, Temp, Sin Camb>}
G_0 = {<?, ?, ?, ?, ?, ?>}

E_1 = <Sol, Temp, Alta, Fue, Temp, Sin Camb> JUEGA=SI
S_1 = {<Sol, Temp, ?, Fue, Temp, Sin Camb>}
G_1 = {<?, ?, ?, ?, ?, ?>}

E_2 =  <Lluv, Frio, Alta, Fue, Temp, Camb    > JUEGA=NO
S_2 = {<Sol , Temp, ?   , Fue, Temp, Sin Camb>}
G_2 = {
       < Sol, ?   , ?   , ?  , ?   , ?       >,
	   <?   , Temp, ?   , ?  , ?   , ?       >,
	   <?   , ?   , ?   , ?  , ?   , Sin Camb>,	   
}

E_3 =  <Sol , Temp, Alta, Fue, Fria, Camb    > JUEGA=SI
S_3 = {<Sol , Temp, ?   , Fue, ?   , ?       >}
G_3 = {
       < Sol, ?   , ?   , ?  , ?   , ?       >,
	   <?   , Temp, ?   , ?  , ?   , ?       >,
}

iii.
5 -> SI pues satisface todo S
6 -> No, pues no satisface ninguna h de G
7 -> No queda claro, no satisface todo S pero sí todo G
8 -> No queda claro, no satisface todo S ni todo G

Ejercicio 3

Considere para el ejercicio anterior un espacio cuyas hipótesis tienen la siguiente forma:
<x,x,x,x,x,x> v <x,x,x,x,x,x>

Por ejemplo: h: <?, Frío, Alto, ?, ?, ?> v <Soleado, ?, Alto, ?, ?, Sin cambios>

a) ¿Cuál es el tamaño del espacio de hipótesis?
b) Calcule el espacio de versiones

a) El tamaño nuevo es el cuadrado del anterior: . Estamos contando hipótesis sintácticamente distintas. Si tomamos la semántica, hay hipótesis equivalentes a otras y en ese caso sólo cuenta una.
b) Otra vez por Candidate-Elimination

E_1 =  <S, T, N, F, T, S> J=SI
S_1 = [
	<S, T, N, F, T, S> v <0, 0, 0, 0, 0, 0>, -- admite solo la inst. #1
]
G_1 = [
	<?, ?, ?, ?, ?, ?> v <0, 0, 0, 0, 0, 0>, -- admite cualquier instancia
]

E_2 =  <S, T, A, F, T, S> J=SI
S_2 = [
	<S, T, ?, F, T, S> v <0, 0, 0, 0, 0, 0>, -- semanticamente igual a <S, T, N, F, T, S> v <S, T, A, F, T, S>
]
G_2 = [
	<?, ?, ?, ?, ?, ?> v <0, 0, 0, 0, 0, 0>,
]

E_3 = <L, F, A, F, T, C> J=NO
S_3 = [
	<S, T, ?, F, T, S> v <0, 0, 0, 0, 0, 0>,
]
G_3 = [
	<S, ?, ?, ?, ?, ?> v <?, T, ?, ?, ?, ?>,
	<S, ?, ?, ?, ?, ?> v <?, ?, ?, ?, ?, S>,
	<?, T, ?, ?, ?, ?> v <?, ?, ?, ?, ?, S>,
]

E_4 = <S, T, A, F, F, C> J=SI
S_4 = [
	<S, T, ?, F, ?, ?> v <0, 0, 0, 0, 0, 0>, -- semanticamente igual a <S, T, ?, F, T, ?> v <S, T, ?, F, F, ?>
]
G_4 = [
	<S, ?, ?, ?, ?, ?> v <?, T, ?, ?, ?, ?>,
	<S, ?, ?, ?, ?, ?> v <?, ?, ?, ?, ?, S>,
	<?, T, ?, ?, ?, ?> v <?, ?, ?, ?, ?, S>,
]

Ejercicio 4

a) Implemente el algoritmo FIND-S para el problema de cuándo Pedro salva un examen.
b) Verifque su algoritmo contra el ejemplo visto en el teórico.
c) Implemente un programa que genere instancias aleatorias, y luego las clasifque de acuerdo al concepto:

¿Cuántos ejemplos únicos (sin repetidos) tiene que generar en promedio para aprender el concepto? ¿Cuántos ejemplos únicos positivos?

Ver código

from random import randrange

atributos_posibles_valores = {
    "Dedicación": ["alta", "media", "baja"],
    "Dificultad": ["alta", "media", "baja"],
    "Horario": ["matutino", "nocturno"],
    "Humedad": ["alta", "media", "baja"],
    "HumorDoc": ["bueno", "malo"],
}


def match(h_i, x_i):
    return h_i != "0" and (h_i == x_i or h_i == "?")


def eval_h(h, x):
    return all(match(h_i, x_i) for h_i, x_i in zip(h, x))


def expr_mas_general(h_i, x_i):
    if h_i == "0":
        return x_i
    else:
        return "?"


def generalizar_h(h, x):
    return tuple(
        h_i if match(h_i, x_i) else expr_mas_general(h_i, x_i) for h_i, x_i in zip(h, x)
    )


def find_s(train):
    h = tuple("0" for _ in atributos_posibles_valores)

    for x, c_x in train:
        if c_x and not eval_h(h, x):
            h = generalizar_h(h, x)

    return h


def test_ejemplo_curso():
    train = [
        (("alta", "alta", "nocturno", "media", "bueno"), True),
        (("baja", "media", "matutino", "alta", "malo"), False),
        (("media", "alta", "nocturno", "media", "malo"), True),
        (("media", "alta", "nocturno", "alta", "bueno"), False),
    ]

    print(find_s(train))


test_ejemplo_curso()


def test_cant_ejemplos():
    concepto = ("?", "media", "?", "?", "?")

    def ejemplo_verdad():
        instancia = tuple(
            posibles_valores[randrange(0, len(posibles_valores))]
            for atributo, posibles_valores in atributos_posibles_valores.items()
        )

        clasif = eval_h(concepto, instancia)
        return instancia, clasif

    def corrida():
        conj_ejemplos = set()
        cant_ejemplos_positivos = 0
        for cant_ejemplos in range(1000):
            while True:
                nuevo = ejemplo_verdad()
                if nuevo not in conj_ejemplos:
                    if nuevo[1]:
                        cant_ejemplos_positivos += 1
                    break

            conj_ejemplos.add(nuevo)
            h_aprendido = find_s(conj_ejemplos)
            if h_aprendido == concepto:
                return cant_ejemplos, cant_ejemplos_positivos

    cant_ejemplos_necesarios = []
    cant_ejemplos_positivos_necesarios = []
    for _ in range(100_000):
        a, b = corrida()
        cant_ejemplos_necesarios.append(a)
        cant_ejemplos_positivos_necesarios.append(b)
    print(
        "promedio cant_ejemplos_necesarios:",
        sum(cant_ejemplos_necesarios) / len(cant_ejemplos_necesarios),
    )
    print(
        "promedio cant_ejemplos_positivos_necesarios:",
        sum(cant_ejemplos_positivos_necesarios)
        / len(cant_ejemplos_positivos_necesarios),
    )


test_cant_ejemplos()

Ejercicio 6

Considere un espacio compuesto de puntos en el plano entero, y un conjunto de hipótesis formadas por rectángulos:

Dados los siguientes ejemplos:
Pasted image 20230815153930.png

Encuentre los conjuntos S y G. Dibújelos en el diagrama.
Si el alumno pudiera elegir el siguiente ejemplo para su entrenamiento, ¿cuál le convendría elegir? ¿Cuál seguramente no?
Si ud. desea enseñar el concepto (3 ≤ x ≤ 5, 2 ≤ y ≤ 9): ¿cuál es la mínima cantidad de ejemplos que ud. debería dar?

1

2

No me convendría ninguno que pertenezca a S.
Me convendría cualquiera que pertenezca a G_0 y G_1 pero que no sea demasiado cercano a S.
Tampoco conviene alguno con alguna coordenada igual a la de otro ejemplo (no aportaría información en ese eje).

3

¿Bajo cualquier algoritmo?
Con 6 ejemplos ya es suficiente, no se me ocurre hacerlo con menos.
Dos positivos abarcando el máximo posible.
4 negativos limitando las 4 direcciones en las que se podría expandir.

Ejercicio 7

Se desea aprender un concepto que se supone es un triángulo rectángulo isósceles en el semiplano |R+ x |R+ , de la siguiente forma:

Pasted image 20230815164217.png

a

Dé TODAS las hipótesis consistentes con el siguiente conjunto de entrenamiento:

(1, 0.5) positivo
(1.1, 5 ) negativo
(2, 0 ) positivo
(8, 0 ) negativo
Muestre cómo llega al resultado paso a paso.

Marco los puntos de ejemplo en el plano (rojo negativo y verde positivo).
Trazo las rectas de la forma y=a-x para cada ejemplo.
Me quedo con aquellas que se corresponden a la hipótesis más general (amarillo) y más específica (azul).
Toda la región entre esas dos rectas son las hipótesis consistentes con el conjunto de entrenamiento.

b

No elegiría ningún punto por fuera de la región hallada. Debajo de la linea verde sé que dará positivo y por arriba de la amarilla dará negativo.

c

Misma lógica que antes.

d

(1, 1) NEG contradice al ejemplo (2, 0) POS.
Ambos puntos pertenecen a la recta y = 2-x.

Debería descartar ambos ejemplos (uno está mal y no sé cuál es) y re-entrenar.

Ejercicio 8

Considere un espacio cuyas hipótesis son, en lugar de conjunciones, disyunciones de restricciones sobre los atributos. Así, por ejemplo, la hipótesis que representa que Pedro juega cuando el viento es suave o cuando está soleado es:
<Soleado, ∅, ∅, Suave, ∅, ∅>

a

Calcule la cantidad de posibles hipótesis sintáctica y semánticamente distintas.

Sintácticamente (igual que con conjunciones):

Semánticamente:

Debemos restarles las que son equivalentes entre sí.
Demasiada combinatoria.

b

Especifique cómo son las reglas de generalización y especificación mínimas para este nuevo espacio.

Supongamos que la hipótesis que queremos cambiar es:
, con
Y la generalización/especificación surge de una inconsistencia con el ejemplo:
, con

Generalización:

Antes era usar la regla .

Especificación:

Se varían los a los valores .
pasa a
Pero con , pasa a